package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KBinaryTree;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;

/**
 *
 */
@KBinaryTree
@KDynamicPlanning
public class LC96_UniqueBinarySearchTrees {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int numTrees(int n) {
            int[] T = new int[n + 1];
            T[0] = 1;
            T[1] = 1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    T[i] += T[j - 1] * T[i - j];
                }
            }
            return T[n];
        }
    }
}
